#include "SingleLinkedList.h"
#include <cstdio>
#include <cstdlib>

int main(int argc, char const *argv[])
{
    LinkList L;
    LNode *search;
    CreatListOnHead(L);
    PrintList(L);
    search = GetElem(L, 2);
    if (search != NULL)
    {
        printf("按序号查找成功\n");
        printf("%d\n", search->data);
    }
    search = LocateElem(L, 6); //按值查询
    if (search != NULL)
    {
        printf("按值查找成功\n");
        printf("%d\n", search->data);
    }
    ListFrontInsert(L, 2, 99); //新结点插入第i个位置
    PrintList(L);
    ListDelete(L, 4); //删除第4个结点
    PrintList(L);
    system("pause");
}

// 头插法新建链表
LinkList CreatListOnHead(LinkList &L)
{
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode)); // 头节点
    L->next = NULL;
    scanf("%d", &x);
    while (x != 9999)
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }

    return L;
}

// 尾插法新建链表
LinkList CreatListOnTail(LinkList &L)
{
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s, *r;
    scanf("%d", &x);
    while (x != 9999)
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }

    r->next = NULL;

    return L;
}

// 按序号查找节点
LNode *GetElem(LinkList L, int i)
{
    if (i == 0)
    {
        return L;
    }
    int j = 1;
    LNode *r = L->next;

    if (i < 1)
    {
        return NULL;
    }
    while (r && j != i)
    {
        r = r->next;
        j++;
    }
    if (j == i)
    {
        return r;
    }

    return NULL;
}

// 按值查找
LNode *LocateElem(LinkList L, ElemType e)
{
    LNode *r = L->next;
    while (r && r->data != e)
    {
        r = r->next;
    }

    return r;
}

// 新结点插入第i个位置
bool ListFrontInsert(LinkList L, int i, ElemType e)
{
    LNode *p = GetElem(L, i - 1);
    if (NULL == p)
    {
        return false;
    }
    LinkList s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;

    return true;
}

// 删除第i个结点
bool ListDelete(LinkList L, int i)
{
    LNode *p = GetElem(L, i - 1);
    if (NULL == p)
    {
        return false;
    }
    LNode *q;
    q = p->next;
    p->next = q->next;
    free(q);

    return true;
}

// 遍历链表
void PrintList(LinkList L)
{
    L = L->next;
    while (L)
    {
        printf("%3d", L->data);
        L = L->next;
    }

    printf("\n");
}
